package com.gorkr.labuladong.data_struct.bt;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class M113PathSumii {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;

            this.right = right;
        }


    }
    private List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return res;
        }
        find(root,new LinkedList<Integer>(),0,targetSum);
        return res;

    }

    public void find(TreeNode node, List<Integer> trace, int sum, int targetSum) {

        sum += node.val;

        ArrayList<Integer> newTrace = new ArrayList<>(trace);
        newTrace.add(node.val);


        if (node.left == null && node.right == null) {
            if(sum==targetSum){
                res.add(newTrace);
            }
            return;
        }

        if(node.left!=null){
            find(node.left,newTrace,sum,targetSum);
        }
        if(node.right!=null){
            find(node.right,newTrace,sum,targetSum);
        }
    }

    @Test
    public void test(){
        TreeNode treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(8);
        treeNode.left.left = new TreeNode(11);
        treeNode.right.left = new TreeNode(13);
        treeNode.right.right = new TreeNode(4);
        treeNode.left.left.left = new TreeNode(7);
        treeNode.left.left.right = new TreeNode(2);
        treeNode.right.right.left = new TreeNode(5);
        treeNode.right.right.right = new TreeNode(1);

        TreeNode root = new TreeNode(-2);
        root.right = new TreeNode(-3);

        System.out.println(pathSum(root, -5));


    }
}
